package com.wushijia.datastructure;

public class Array{
    public static void print(int[] table)               
    {
        if (table!=null)
            for (int i=0; i<table.length; i++)
                System.out.print(" "+table[i]);
        System.out.println();
    }

    public static void insertSort(int[] table)            
    { 
    	System.out.println("insertSort:");                                                
        for (int i=1; i<table.length; i++)            
        {
            int temp=table[i], j;                      
            for (j=i-1; j>-1 && temp<table[j]; j--)     
            {
                table[j+1] = table[j];
            }
            table[j+1] = temp;                        
            System.out.print("after "+i+" insert: ");
            print(table);
        }
    }

    public static void shellSort(int[] table)        
    {
    	System.out.println("shellSort:");
        for (int delta=table.length/2; delta>0; delta/=2)  
        {
            for (int i=delta; i<table.length; i++)       
            {
                int temp = table[i];                 
                int j=i-delta;                          
                while (j>=0 && temp<table[j])           
                {
                    table[j+delta] = table[j];
                    j-=delta;                           
                } 
                table[j+delta] = temp;                  
            }
            System.out.print("    delta="+delta+"     ");
            print(table);
        }
    }

    public static void bubbleSort(int[] table)            
    {
    	System.out.println("bubbleSort:");
        boolean exchange=true;                           
        for (int i=1; i<table.length && exchange; i++)    
        {
            exchange=false;                             
            for (int j=0; j<table.length-i; j++)      
                if (table[j]>table[j+1])                
                {
                    int temp = table[j];
                    table[j] = table[j+1];
                    table[j+1] = temp;
                    exchange=true;                      
                }
            System.out.print("after "+i+" bubble: ");
            print(table);
        }
    }

    private static void quickSort(int[] table, int low, int high) 
    {                                                   
        if (low<high)                                   
        {
             int i=low, j=high;
             int vot=table[i];                          
             while (i!=j)                             
             {
                 while (i<j && vot<=table[j])            
                     j--;
                 if (i<j)
                 {
                     table[i]=table[j];               
                     i++;
                 }     
                 while (i<j && table[i]<vot)             
                     i++;
                 if (i<j)
                 {
                     table[j]=table[i];                
                     j--;
                 }     
             }
            table[i]=vot;                               
            System.out.print(low+".."+high+",  vot="+vot+"  ");
            print(table);
            quickSort(table, low, j-1);              
            quickSort(table, i+1, high);           
        }
    }
    
    public static void quickSort(int[] table)            
    {
        System.out.println("quickSort:");
        quickSort(table, 0, table.length-1);
    }

    public static void selectSort(int[] table)         
    {
        System.out.println("selectSort:");
        for (int i=0; i<table.length-1; i++)            
        {                                              
            int min=i;                                  
            for (int j=i+1; j<table.length; j++)        
                if (table[j]<table[min])
                     min = j;                           

            if (min!=i)                              
            {
                int temp = table[i];
                table[i] = table[min];
                table[min] = temp;
            }
            System.out.print(""+i+": ");
            print(table);
        }
    }

    private static void sift(int[] table, int low, int high) 
    {                                           
        int i=low;                                  
        int j=2*i+1;                                  
        int temp=table[i];                              
        while (j<=high)                                
        {                                                  
            if (j<high && table[j]>table[j+1])        
                j++;                                      
            if (temp>table[j])                     
            {
                table[i]=table[j];           
                i=j;                                
                j=2*i+1;
            }
            else
                j=high+1;                           
        }
        table[i]=temp;                               
        System.out.print("sift  "+low+".."+high+"  ");
        print(table);
    }

    public static void heapSort(int[] table)
    {
        System.out.println("heapSort:");
        int n=table.length;
        for (int j=n/2-1; j>=0; j--)                   
            sift(table, j, n-1);        
        for (int j=n-1; j>0; j--)                       
        {
            int temp = table[0];
            table[0] = table[j];
            table[j] = temp;
            sift(table, 0, j-1);
        }
    }

    private static void merge(int[] X, int[] Y, int m, int r, int n)   
    {
        int i=m, j=r, k=m;
        while (i<r && j<r+n && j<X.length)             
            if (X[i]<X[j])                               
                Y[k++]=X[i++];
            else
                Y[k++]=X[j++];

        while (i<r)                                      
            Y[k++]=X[i++];
        while (j<r+n && j<X.length)                        
            Y[k++]=X[j++];
    }
    
    private static void mergepass(int[] X, int[] Y, int n)
    {
        System.out.print("sublist's length is: "+n+"  ");
        int i=0;
        while (i<X.length-2*n+1)
        {
            merge(X,Y,i,i+n,n);
            i += 2*n;
        }
        if (i+n<X.length)
            merge(X,Y,i,i+n,n);                          
        else  
            for (int j=i; j<X.length; j++)               
                Y[j]=X[j];
    }

    public static void mergeSort(int[] X)              
    {
        System.out.println("mergeSort:");
        int n=1;                                      
        int[] Y = new int[X.length];                    
        do
        {
            mergepass(X, Y, n);                        
            print(Y);
            n*=2;                                     

            if (n<X.length)
            {
                mergepass(Y, X, n);                 
                print(X);
                n*=2;
            }
        } while (n<X.length);
    }
    
    public static void main(String[] args)
    {       

        int[] table = {32,26,87,72,26,17};     
        System.out.print("data list is:   ");
        Array.print(table);
		Array.insertSort(table);

/*
        int[] table = {27,38,65,97,76,13,27,49,55,4};     
        System.out.print("data list is:   ");
        Array.print(table);
		Array.shellSort(table);
*/
/*
        int[] table = {32,26,87,72,26,17};     
        System.out.print("data list is:   ");
        Array.print(table);
		Array.bubbleSort(table);
*/
/*
        int[] table = {4,5,8,1,2,7,3,6};     
        System.out.print("data list is:   ");
        Array.print(table);
		Array.bubbleSort(table);		
*/
/* 
        int[] table = {38,26,97,19,66,1,5,49};     
        System.out.print("data list is:   ");
        Array.print(table);
		Array.quickSort(table);	
*/
/*
        int[] table = {32,26,87,72,26,17};     
        System.out.print("data list is:   ");
        Array.print(table);
		Array.selectSort(table);
*/
/*
        int[] table = {38,26,97,19,66,1,5,49};     
        System.out.print("data list is:   ");
        Array.print(table);
		Array.selectSort(table);
/*
        int[] table = {81,49,76,27,97,38,49,13,65};     
        System.out.print("data list is:   ");
        Array.print(table);
		Array.heapSort(table);
*/
/*
        int[] table = {52,26,97,19,66,8,49};     
        System.out.print("data list is:   ");
        Array.print(table);
		Array.mergeSort(table);
*/
    }
}